package org.mozhu.learning.algo.binary_search;

/**
 * 一、四种常见的二分查找变形问题
 1. 查找第一个值等于给定值的元素
 2. 查找最后一个值等于给定值的元素
 3. 查找第一个大于等于给定值的元素
 4. 查找最后一个小于等于给定值的元素
 */
public class BinarySearchExt {

    // 1. 查找第一个值等于给定值的元素
    public int firstIndexOf(int[] a, int value) {
        int low = 0;
        int high = a.length - 1;
        if (a[low] > value || a[high] < value) return -1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] == value) {
                if (mid == 0 || a[mid - 1] != value) return mid;
                high = mid - 1;
            } else if (a[mid] > value) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    // 2. 查找最后一个值等于给定值的元素
    public int lastIndexOf(int[] a, int value) {
        int low = 0;
        int high = a.length - 1;
        if (a[low] > value || a[high] < value) return -1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] == value) {
                if (mid == a.length - 1 || a[mid + 1] != value) return mid;
                low = mid + 1;
            } else if (a[mid] > value) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    // 3. 查找第一个大于等于给定值的元素
    public int firstGreaterThanOrEquals(int[] a, int value) {
        int low = 0;
        int high = a.length - 1;
        if (a[low] > value || a[high] < value) return -1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] >= value) {
                if (mid == 0 || a[mid - 1] < value) return mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    // 4. 查找最后一个小于等于给定值的元素
    public int lastLessThanOrEquals(int[] a, int value) {
        int low = 0;
        int high = a.length - 1;
        if (a[low] > value || a[high] < value) return -1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] <= value) {
                if (mid == a.length - 1 || a[mid + 1] > value) return mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}
